現代處理器使用一種稱為 虛擬位址。 虛擬記憶體（VM） 是主記憶體的一種抽象，為每個行程提供一個私有的、連續的 線性位址空間。
1. 位址的演進
在 實體位址 （圖 9.1）中，中央處理器會直接將 實體位址（PA） 傳送至動態隨機存取記憶體（DRAM）。在 虛擬位址 （圖 9.2）中，處理器產生一個 虛擬位址（VA），此位址由 記憶體管理單元（MMU） 轉換成實體位址後才進行記憶體存取。
2. 層次結構與快取
DRAM 充當 DRAM 快取 磁碟儲存的快取。由於磁碟延遲問題，系統採用 寫回策略。位址翻譯透過 TLB 利用 TLB 索引（TLBI） 並以如 PROT_WRITE等保護位來確保安全。大型位址空間（$N = 2^n$）可支援複雜的 區段 以及 作業系統針對輸入/輸出裝置提供的服務。
main.py
TERMINALbash — 80x24
> Ready. Click "Run" to execute.
>
QUESTION 1
[Fill in the blanks] Complete the following table for a Virtual Address Space where $N = 2^n$ and the largest address is $N-1$. Use units: $K=2^{10}, M=2^{20}, G=2^{30}, T=2^{40}, P=2^{50}, E=2^{60}$.
n=16: N=64K, Max=0xFFFF; n=32: N=4G, Max=0xFFFFFFFF; n=48: N=256T, Max=0xFFFFFFFFFFFF; n=64: N=16E, Max=0xFFFFFFFFFFFFFFFF
n=16: N=16K; n=32: N=32M; n=48: N=48G; n=64: N=64T
✅ Correct!
Correct. Virtual address space growth is exponential. $2^{16}=64K$, $2^{32}=4G$, $2^{48}=256T$, and $2^{64}=16E$.❌ Incorrect
Recall that $N = 2^n$. $2^{10}$ is 1K, $2^{20}$ is 1M, $2^{30}$ is 1G, etc.QUESTION 2
Why does the DRAM cache use a Write-back policy instead of Write-through?
To maintain Stack Discipline.
Due to the massive latency penalty of accessing disk storage.
To prevent internal fragmentation.
Because the L3 unified cache is 16-way associative.
✅ Correct!
Correct. Synchronizing with the disk on every write would be too slow, so updates are deferred until swapping occurs.❌ Incorrect
Disk access is roughly 100,000 times slower than DRAM; writing back only when necessary is vital.QUESTION 3
What happens if a process attempts to write to a page where the PTE has PROT_WRITE set to 0?
A General protection fault occurs.
The MMU performs Swapping automatically.
Deferred coalescing is triggered.
The Reference bit (A bit) is cleared.
✅ Correct!
Correct. The MMU hardware checks protection bits during address translation; violations trigger an exception (segfault/GPF).❌ Incorrect
Protection bits are enforced by hardware to ensure process isolation in the virtual address space.QUESTION 4
Which component is responsible for translating the Virtual Address to a Physical Address?
The L3 unified cache (8 MB, 16-way).
The Memory Management Unit (MMU).
The Rio Package.
The Buddy System Allocator.
✅ Correct!
Correct. The MMU is the hardware that performs the mapping using page tables and the TLB.❌ Incorrect
The MMU sits between the CPU and main memory specifically for this translation.QUESTION 5
What is the physical address (PA) if the MMU finds a mapping for a VA where VPN=0x0d and VPO=0x14, given PPN=0x0d?
PA = 0x354: PPN=0x0d, PPO=0x14
$PA = 0x140d$
$PA = 0x0001$
PA = 0x354: VPN=0x0d, VPO=0x14
✅ Correct!
Correct. PPO is identical to VPO. PA is the concatenation of PPN and PPO.❌ Incorrect
During translation, the offset (VPO) stays the same (becomes PPO), while the VPN is mapped to a PPN.Case Study: Advanced Heap Management & VM Translation
Optimizing Allocators and Address Translation Efficiency
You are designing a high-performance allocator for an Intel Core i7 system with a k-level page table hierarchy. The allocator uses a single global variable (heap_listp) and must minimize external fragmentation using Buddy System Allocation. You also need to modify the block structure to improve Peak memory utilization.
Q
1. Implement the 'find_fit' function for a simple implicit list allocator using first-fit logic. Your solution must account for Internal fragmentation and return NULL if no block is found.
Solution:
Implementation: static void *find_fit(size_t asize) { void *bp; /* Iterate through the heap starting from heap_listp */ for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) { /* If block is not allocated and size is sufficient */ if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) { return bp; } } return NULL; /* No fit found */ } This function searches the linear heap space, balancing search speed with memory utilization.
Implementation: static void *find_fit(size_t asize) { void *bp; /* Iterate through the heap starting from heap_listp */ for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) { /* If block is not allocated and size is sufficient */ if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) { return bp; } } return NULL; /* No fit found */ } This function searches the linear heap space, balancing search speed with memory utilization.
Q
2. Explain how to modify an allocator to remove boundary tags (footers) from allocated blocks. How does this affect Peak memory utilization and the mm_free(void *bp) logic?
Solution:
To remove footers in allocated blocks, we store an 'extra' bit in the header of the *next* block to indicate whether the *current* block is allocated. This allows us to reduce the minimum block size by one word, directly increasing Peak memory utilization by reducing internal fragmentation in small objects. However, mm_free and coalesce(bp) must now inspect the header of the next block to determine if the previous block can be merged, maintaining constant-time coalescing for free blocks (which still require footers).
To remove footers in allocated blocks, we store an 'extra' bit in the header of the *next* block to indicate whether the *current* block is allocated. This allows us to reduce the minimum block size by one word, directly increasing Peak memory utilization by reducing internal fragmentation in small objects. However, mm_free and coalesce(bp) must now inspect the header of the next block to determine if the previous block can be merged, maintaining constant-time coalescing for free blocks (which still require footers).
Q
3. Describe the 'Buddy System Allocation' process for a block of size 32 bytes at address xxx...x10000. How does it handle recursive splitting?
Solution:
The Buddy System finds a block of size $2^j$ where $k \le j \le m$. To allocate 32 bytes ($2^5$), if only a $2^7$ block is available, it splits into two $2^6$ buddies. One $2^6$ block is then split again into two $2^5$ buddies. One buddy at address xxx...x10000 is allocated, while its buddy (address xxx...x11000) remains free. This minimizes external fragmentation and allows for fast buddy-merging using bitwise address operations.
The Buddy System finds a block of size $2^j$ where $k \le j \le m$. To allocate 32 bytes ($2^5$), if only a $2^7$ block is available, it splits into two $2^6$ buddies. One $2^6$ block is then split again into two $2^5$ buddies. One buddy at address xxx...x10000 is allocated, while its buddy (address xxx...x11000) remains free. This minimizes external fragmentation and allows for fast buddy-merging using bitwise address operations.